#define MAX_SIZE 128

typedef struct Node_ {
    char words[MAX_SIZE];
    int count;
} Node;

typedef struct Dict_ {
    int size;
    int cap;
    Node *arr;
} Dict;

int Compare(const void *p1, const void *p2) 
{
    Node *n1 = (Node *)p1;
    Node *n2 = (Node *)p2;
    if (n1->count != n2->count) {
        return n2->count - n1->count;
    }
    return strcmp(n1->words, n2->words);
}


void InitDict(Dict *dict, int cap)
{
    dict->size = 0;
    dict->cap = cap;
    dict->arr = (Node *)malloc(sizeof(Node) * cap); 
    memset(dict->arr, 0, sizeof(Node) * cap);
}

void AddDict(Dict *dict, char *words)
{
    strcpy(dict->arr[dict->size].words, words); 
    dict->arr[dict->size].count = 1;
    ++dict->size;
}

void FreeDict(Dict *dict)
{
    free(dict->arr);
}

char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize)
{
    Dict dict;
    InitDict(&dict, wordsSize);

    for (int i = 0; i < wordsSize; ++i) {
        int repeat = 0;
        for (int j = 0; j < dict.size; ++j) {
            if (!strcmp(words[i], dict.arr[j].words)) {
                ++dict.arr[j].count;
                repeat = 1;
                break;
            }
        }
        if (!repeat) {
            AddDict(&dict, words[i]);
        }
    }

    qsort(dict.arr, dict.size, sizeof(Node), Compare);
    char **res = (char **)malloc(sizeof(char *) * k);
    for (int i = 0; i < k; ++i) {
        res[i] = (char *)malloc(sizeof(char) * MAX_SIZE);
        strcpy(res[i], dict.arr[i].words);
    }
    *returnSize = k;
    FreeDict(&dict);
    return res;
}



#define POOL_SIZE   10000
typedef struct _info_st
{
    char *key;
    int val;
    UT_hash_handle hh;
}info_st;

int compare(info_st *a, info_st *b)
{
    if(a->val != b->val)
    {
        return b->val - a->val;
    }
    else
    {
        return strcmp(a->key, b->key);
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
// 【算法思路】hash+排序。字符串指针作为key，注意uthash函数的使用
char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize){
    if(wordsSize == 0 || k == 0)
    {
        *returnSize = 0;
        return NULL;
    }

    info_st * head = NULL;
    info_st * pool = (info_st *)calloc(POOL_SIZE, sizeof(info_st));
    int psize = 0;

    for(int i = 0; i < wordsSize; i++)
    {
        info_st *cur = &pool[psize];
        cur->key = words[i];
        cur->val = 1;

        //printf("<%d>%s  ", i, cur->key);

        info_st *tmph;
        HASH_FIND(hh, head, cur->key, strlen(cur->key), tmph);
        //HASH_FIND(hh, head, words[i], strlen(words[i]), tmph);

        if(tmph == NULL)
        {
            HASH_ADD_KEYPTR(hh, head, cur->key, strlen(cur->key), cur);
            psize++;
            continue;
        }

        tmph->val++;
    }
    //printf("\n");

    HASH_SORT(head, compare);

    char **res = (char **)calloc(psize, sizeof(char*));
    int rsize = 0;

    info_st *cur, *tmph;

    int id = 0;
    HASH_ITER(hh, head, cur, tmph)
    {
        //printf("<%d>[%s %d]   ", id, cur->key, cur->val);

        res[rsize++] = cur->key;
        id++;
        if(id == k)
        {
            //break;
        }
    }

    *returnSize = k;
    return res;
}

